package leetcode;

import java.util.*;
class Node1 {
    public int val;
    public Node1 left;
    public Node1 right;

    public Node1() {}

    public Node1(int _val) {
        val = _val;
    }

    public Node1(int _val, Node1 _left, Node1 _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
public class LeetCodeMain118 {

    public boolean exist(char[][] board, String word) {
        if (board==null|board.length==0||board[0]==null||board[0].length==0){
            return false;
        }
        char[] arr=word.toCharArray();
        boolean[][] flag=new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (back(board,arr,flag,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean back(char[][] board,char[] arr,boolean[][] flag,int x,int y,int num){
        if (x<0||y<0||x>=board.length||y>=board[0].length||board[x][y]!=arr[num]||flag[x][y]){
            return false;
        }
        if (num==arr.length-1){
            return true;
        }
        flag[x][y]=true;
        boolean ans=false;
        ans=back(board, arr, flag, x+1, y, num+1)||
                back(board, arr, flag, x-1, y, num+1)||
                back(board, arr, flag, x, y+1, num+1)||
                back(board, arr, flag, x, y-1, num+1);
        flag[x][y]=false;
        return ans;
    }
    int pre=0;
    public TreeNode reConstructBinaryTreeChild(int[] preorder,int[] inorder,int vins,int last){
        if (vins>last){
            return null;
        }
        TreeNode root=new TreeNode(preorder[pre]);
        int postions=postion(inorder,vins,last,preorder[pre]);
        pre++;
        root.left=reConstructBinaryTreeChild(preorder, inorder, vins, postions-1);
        root.right=reConstructBinaryTreeChild(preorder, inorder, postions+1, last);
        return root;
    }
    public int postion(int[] inorder,int vins,int last,int num){
        for (int i = 0; i <= last; i++) {
            if (inorder[i]==num){
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null){
            return null;
        }
        TreeNode root=reConstructBinaryTreeChild(preorder,inorder,0,inorder.length-1);
        return root;
    }

    List<Node1> list=new ArrayList<>();
    public Node1 treeToDoublyList(Node1 root) {
        if (root==null){
            return null;
        }
        inOrder(root);
        int size=list.size();

        for (int i = 0; i < size-1; i++) {
            list.get(i).right=list.get(i+1);
        }
        for (int i = 1; i < size; i++) {
            list.get(i).left=list.get(i-1);
        }
        list.get(0).left=list.get(size-1);
        list.get(size-1).right=list.get(0);
        return list.get(0);
    }
    public void inOrder(Node1 root){
        if (root==null){
            return;
        }
        inOrder(root.left);
        list.add(root);
        inOrder(root.right);
    }
    List<List<Integer>> res=new ArrayList<>();
    List<Integer> data=new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        DFS(root,target,0);
        return res;
    }
    public void DFS(TreeNode root,int target,int sum){
        if (root==null){
            return;
        }
        sum+=root.val;
        data.add(root.val);
        if (sum==target&&root.left==null&&root.right==null){
            res.add(new ArrayList<>(data));
        }
        DFS(root.left, target, sum);
        DFS(root.right, target, sum);
        sum-=root.val;
        data.remove(data.size()-1);

    }
    public int singleNumber(int[] nums) {
        int res=0;
        for (int i = 0; i < 32; i++) {
            int count=0;
            for (int num:nums) {
                if ((num&(1<<i))!=0){
                    count++;
                }
            }
            if (count%3==1){
                res^=(1<<i);
            }
        }
        return res;
    }
    public int[] singleNumbers(int[] nums) {
        int num=0,a=0,b=0;
        for (int n:nums) {
            num^=n;
        }
        int div=1;
        while ((div&num)==0){
            div<<=1;
        }
        for (int n:nums) {
            if ((div&n)!=0){
                a^=n;
            }else {
                b^=n;
            }
        }
        return new int[]{a,b};

    }
}
